2021 Algorithm                       < No.8 이상한 놈>                  Prof. Zoh Q.

2022 Algorithm                     < No.12 울트라 마라톤>                     Prof. Zoh Q.

울트라 마라톤

[문제]    울트라 마라톤(ultra marathon)은 일반 마라톤 구간인 42.195km 이상을 달리는 스포츠다. 예를 들어 서울에서 부산까지, 도쿄에서 아오모리까지 달리는 것이 전형적인 울트라 마라톤에 속한다. 울트라 마라톤에는 두 가지 타입이 있다. 하나는 특정 거리, 예를 들어 100km를 달리는 것이고, 다른 하나는 특정 시간 동안(예를 들면 24시간이나 48시간) 달린 후 더 먼 거리를 달린 선수가 승자가 된다. 가장 긴 거리를 달리는 대회로는 미국에서 개최되는 3100마일(4989km)을 달리는 “미친” 대회도 있었다.

100km 대회 세계 기록은 남자의 경우 일본의 스나다 다카히로(砂田貴裕)가 보유한 6시간 13분 33초이고, 여자의 경우 역시 일본의 아베 도모에(安部友恵)가 보유한 6시간 33분 11초이다.

우리는 울트라 마라톤 대회를 도심에서 개최하려고 한다. 따라서 지금의 도심에서 가장 긴 마라톤 코스의 길이가 얼마나 되는지 이것을 계산해보려고 한다. 이 길이가 충분히 길지 않으면 다른 도시를 찾아야 한다. 입력 도시의 도로망의 형식은 앞선 문제와 같다. 두 교차로 [eqn: x,y]를 연결하는 지나는 도로[eqn: (x,y)]는 모두 정수(km) 길이를 가진 edge이다. 도시의 각 교차로(vertex)는 알파벳 소문자 1자로 표시된다. 따라서 도시는 최대 26개의 정점을 가진 vertex로 표현된다. 출발은 앞 문제와 같이 지점 a에서 출발하고 지점을 종복 방문하지 않고 다시 시작점 a로 되돌아와야 한다. 우리가 완성해야 할 마라톤 코스는 다음의 성질을 만족해야 한다.

1) 출발점 vertex는 항상 스타디움이 위치한 a로 고정되어 있다.

2) 마라톤 코스는 선수들이 헛갈리지 않도록 같은 장소를 재방문하지 않도록 설계되어야 한다. 즉 마라톤 코스에서 출발점을 제외한 모든 점은 서로 달라야 한다.

이번 문제에서 여러분은 위 두 조건을 만족하는 가장 긴 코스의 정수 길이(km)만을 출력하면 된다. 앞선 문제와 다르게 거쳐 간 경로 전체를 출력하는 것이 아닌 코스의 길이, 즉 하나의 정수만 출력하면 된다. 어떤 경우 도심의 도로망이 분리(disconnected)될 수도 있음을 고려해야 한다.

그림-1. 울트라 마라톤 대회가 열린 도시 도로망의 예

[입출력]    입력과 출력은 앞서 문제와 같이 표준입출력을 사용한다. 입력 파일의 첫 줄에는 정점(vertex)의 수 [eqn: N]과 edge의 수 [eqn: M]이 주어진다. 이어지는 M개의 각 줄에는 두 정점의 vertex [eqn: u~ v]와 이 둘 간의 거리 [eqn: d_u,v]가 정수로 주어진다. 단 앞에 나오는 정점의 알파벳 순서가 뒤 정점보다 더 빠르다. 따라서 모든 edge (u,v)는 입력 파일에 한 번만 나타난다. 그리고 edge의 길이(km)를 나타내는 weight 값의 범위는 [eqn: 1 leq d_u,v `leq 20] 이다. edge가 나타나는 순서는 random 하다.

vertex 이름은 항상 연속된 알파벳 순서는 아닐 수 있다. 즉 특정한 vertex는 빠질 수도 있다. 출력은 a에서 출발하여 돌아오는 마라톤 코스의 최대 길이 정수이다.

모든 입력 데이터에서 정점의 수가 N이라면 edge의 개수 M은 N의 4배를 넘지 않는다. 즉 M < 4N. 즉 그래프의 차수는 대략 평균 6 정도로, 전체 도로망은 상당히 sparse 하다고 가정하면 된다.

[예제 1]

stdin		stdout
14 21 //N, M a f 13 a b 5 d g 2 i j 1 a g 6 e k 2 h k 5 c i 3 f m 1 b m 7	b h 4 k l 1 d i 4 j n 4 j l 15 e m 6 f l 10 d n 1 a n 10 b c 3 h i 5	77 // a-b-m-e-k-h- i-d-n-j-l-f

[제출조건]  프로그램의 이름은 ultra.{py,cpp, java, c}로 한다. 이번 과제의 test case별 허용 수행시간은 10초이며 최대 30번까지 제출 가능하다. 만점자 중에서 전체 수행시간 합으로 가장 빠른 5명과 가장 우아한 코드를 제공한 3명에서 추가 10%의 가점을 주어진다.

stdin		stdout
17 27 a f 12 a c 16 a m 2 f r 2 d f 10 d n 4 c d 16 a c 16 m p 5 m r 3 n p 3 c p 8 d k 8	k h 10 k t 9 e k 5 e t 8 t w 3 o w 8 g o 8 e g 12 e j 8 e w 8 g j 3 g s 2 j s 10 j h 10	61 // a-c- d-n- p-m- r-f

[예제 2]

[도움말]    예제 [2]의 경우에서 볼 수 있듯이 edge (d,k)를 지나면 다시 a로 되돌아오는 정상적인 경로가 없으므로 이 방향으로는 답이 나올 수 없습니다. 따라서 이 아래 모든 case는 cut이 되겠죠. 즉 지나온 edge를 모두 없애면서 나아갈 때 어느 시점에서 다시 a로 돌아오는 길이 없는 경우라면 모두 bound 시켜야겠죠. 즉 현재 도착지점 t에서 a로 가는 길이 있는지, 즉 connected 되어있는지 아닌지를 Graph BFS를 사용하면 빠르게 알 수 있으니까 좀 더 빠르게 계산할 수 있지 않을까요? 물론 connected를 확인하기 위한 BFS를 빠르게 수행할 수 있어야 하겠지만.

[예제 3]

stdin		stdout
18 32 a t 4 a j 7 a n 8 b c 4 b s 3 c r 2 c f 2 c q 2 c k 2 d h 2 d n 3 d w 3 d s 2 e k 7 e m 8 f j 4	f q 4 f t 2 h r 2 h m 3 h w 3 j p 8 j t 2 k q 8 k r 4 m r 3 m w 7 n s 4 n o 7 o w 8 p q 7 s t 2	90 // a-j-p- q-f-c- b-s-d- h-r-k- e-m-w- o-n